/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
    if(heights.length === 0)return 0;
    if(heights.length === 1)return heights[0];

    heights.push(0);

    let area = 0,
        length = heights.length,
        cur = 0,
        stack = [];

    while(cur<length){
        //console.log("~~~",cur);
        if(stack.length === 0){
            stack.push({v:heights.shift(),i:++cur});
        }

        let tmp = heights.shift();
        cur++;

        //console.log("!!!",cur,"tmp",tmp,stack[stack.length-1].v);

        if(tmp>=stack[stack.length-1].v){
            stack.push({v:tmp,i:cur});
        }else{
            let s = stack.pop();
            //console.log(s,stack[stack.length-1]);
            while(stack.length>0 && s.v === stack[stack.length-1].v){
                s = stack.pop();
            }
            let tmpArea = s.v*(cur - s.i);

            //console.log("tmpArea",tmpArea,"tmp",0,"cur",cur,"s",s);

            if(area<tmpArea)area = tmpArea;

            if(stack.length===0){
                stack.push({v:tmp,i:s.i});
            }else if(tmp>=stack[stack.length-1].v){
                stack.push({v:tmp,i:s.i});
            }else{
                stack.push({v:stack[stack.length-1].v,i:s.i});
            }

            //if(tmp!=0)stack.push({v:tmp,i:s.i});
            heights.unshift(tmp);
            cur--;
            //console.log(cur,"heights",heights,"stack",stack);
        }
    }
    //console.log(cur);

    return area;
};


console.log(largestRectangleArea([4,2,2,5]));